﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace schedule
{
    class CircularArray<T>
    {
        int logCapacity;
        T[] currentTasks;

        public CircularArray(int myLogCapacity)
        {
            logCapacity = myLogCapacity;
            currentTasks = new T[1 << logCapacity];
        }

        public int capacity
        {
            get { return 1 << logCapacity; }
        }

        public T get(int i)
        {
            return currentTasks[i % this.capacity];
        }

        public void put(int i, T task)
        {
            currentTasks[i % this.capacity] = task;
        }

        public CircularArray<T> resize(int bottom, int top)
        {
            CircularArray<T> newTasks = new CircularArray<T>(logCapacity + 1);
            for (int i = 0; i < bottom; ++i)
                newTasks.put(i, this.get(i));

            return newTasks;
        }
    }


    class UnboundedDEQueue<T> : IDEQueue<T>
    {
        static int LOG_CAPACITY = 2;
        volatile CircularArray<T> tasks;
        public volatile int bottom;
        public int top;

        public UnboundedDEQueue()
        {
            tasks = new CircularArray<T>(LOG_CAPACITY);
            top = 0;
            bottom = 0;
        }

        bool IDEQueue<T>.isEmpty()
        {
            return bottom <= top;
        }

        void IDEQueue<T>.pushBottom(T obj)
        {
            int oldBottom = bottom;
            int oldTop = top;
            CircularArray<T> currentTasks = tasks;
            int size = oldBottom - oldTop;

            if (size >= currentTasks.capacity - 1)
            {
                currentTasks = currentTasks.resize(oldBottom, oldTop);
                tasks = currentTasks;
            }

            tasks.put(oldBottom, obj);
            bottom = oldBottom + 1;
        }

        T IDEQueue<T>.popTop()
        {
            int oldTop = top;
            int newTop = oldTop + 1;
            int oldBottom = bottom;
            CircularArray<T> currentTasks = tasks;
            int size = oldBottom - oldTop;
            if (size <= 0)
                return default(T);

            T obj = tasks.get(oldTop);
            if (Interlocked.CompareExchange(ref top, newTop, oldTop) == oldTop)
                return obj;

            return default(T);
        }

        T IDEQueue<T>.popBottom()
        {
            CircularArray<T> currentTasks = tasks;
            --bottom;
            int oldTop = top;
            int newTop = oldTop + 1;
            int size = bottom - oldTop;
            if (size < 0)
            {
                bottom = oldTop;
                return default(T);
            }

            T obj = tasks.get(bottom);
            if (size > 0)
                return obj;

            if (Interlocked.CompareExchange(ref top, newTop, oldTop) != oldTop)
                return default(T);
            bottom = oldTop + 1;
            return obj;
        }
    }
}
